// https://leetcode.cn/problems/flood-fill/description/

// 算法思路总结：
// 1. 广度优先搜索实现洪水填充算法
// 2. 从起始像素开始，向四方向扩展相同颜色的相邻像素
// 3. 使用队列进行BFS遍历，修改颜色值
// 4. 提前判断新旧颜色是否相同，避免无效操作
// 5. 边界检查确保不越界访问数组
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <algorithm>

void printResult(const vector<vector<int>>& result) 
{
    cout << "[";
    for (int i = 0; i < result.size(); ++i) 
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); ++j) 
        {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

class Solution 
{
public:
    typedef pair<int, int> PII;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        int prev = image[sr][sc];
        int m = image.size(), n = image[0].size();
        if (prev == color) return image;

        queue<PII> q;
        q.push({sr, sc});
        image[sr][sc] = color;

        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x < m && x >= 0 && y < n && y >= 0 && image[x][y] == prev)
                {
                    q.push({x, y});
                    image[x][y] = color;
                }
            }
        }

        return image;
    }
};

int main()
{
    int sr1 = 1, sc1 = 1, color1 = 2;
    vector<vector<int>> image1 = {
        {1, 1, 1},
        {1, 1, 0}, 
        {1, 0, 1}
    };
    
    int sr2 = 0, sc2 = 0, color2 = 0;
    vector<vector<int>> image2 = {
        {0, 0, 0},
        {0, 0, 0}
    };

    Solution sol;

    auto vv1 = sol.floodFill(image1, sr1, sc1, color1);
    auto vv2 = sol.floodFill(image2, sr2, sc2, color2);

    printResult(vv1);
    printResult(vv2);

    return 0;
}